High quality and low bit-rate videos are widely used in telecommunication, entertainment, broadcasting, surveillance, digital camera, and military applications. Increasing number of video products, such as DVD players, digital TV, personal video recorders, multimedia jukeboxes, video-capable cell phones, to name a few, rely on video compression to reduce the number of bits required to store and/or transmit a video sequence.
A video sequence consists of a series of frames. To improve video data compression efficiency, motion estimation may be performed. Motion estimation has proven to be effective in exploiting temporal redundancy of a video sequence by extracting correlation between adjacent frames. In a sequence of frames, a current frame is predicted from a previous frame known as a reference frame. The current frame is usually divided into blocks or macroblocks. The size of the macroblocks is typically 16×16 pixels, but may vary, depending on a standard. Each macroblock in the current frame is compared to regions of the same size, which can also be referred to as macroblocks, in the reference frame in an attempt to locate the best matching macroblock, using some error criteria, such as, for example, a sum of absolute differences (SAD), a minimum squared error (MSE), or a mean absolute error (MAE).
To minimize computational costs, motion estimation may be conducted over a predetermined search area within the reference frame. A vector denoting the displacement of the best matching macroblock in the reference frame with respect to the macroblock in the current frame, is determined. This vector is referred to as a motion vector. Motion vectors are typically used to compress video sequences by encoding the changes to an image from one frame to the next rather than the entire frame.
To satisfy the high demand for visual communication applications, many video compression standards have been developed. Motion estimation is a central part of many video compression schemes, such as, for example, ISO/IEC MPEG-1, MPEG-2, MPEG-4, CCITT H.261, ITU-T H.263, ITU-T H.264, and Microsoft WMV9/VC-1. Motion estimation can also be used in other applications besides video compression, such as, for instance, image stabilization, computer vision, motion segmentation, and video analysis.
A typical motion estimation module in a video encoding system is usually the most computationally intensive component and is responsible for about 50-60%, in some cases up to 80%, of the total cost in terms of computation time and power. Although much work has been done to develop efficient motion estimation algorithms, most prior work targets very-large-scale integration (VLSI) systems, and is not software friendly. The hardware-oriented algorithms do not provide sufficient flexibility and require additional resources. A strict software implementation of these algorithms may not achieve the same level of efficiency. In development of many motion estimation algorithms, the number of computational operations is used for measurement of their computational complexity. Very few algorithms have been developed that optimize both computational performance and memory access bandwidth, which are significant constraints for a resource-limited embedded system.